import demo.MyQueue;

import java.util.Stack;

public class Test {
    /**
     * 模拟实现队列
     * @param args
     */
    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.offer(1);
        myQueue.offer(2);
        myQueue.offer(3);
        myQueue.offer(4);
        myQueue.offer(5);
        System.out.println(myQueue.poll());
        System.out.println(myQueue.peek());
        System.out.println(myQueue.isEmpty());
    }
    /**栈的压入 弹出序列
     1.入栈
     2.判断是否相等
     3.相等,i++,j++,出栈,不等,i++
     */
    public static boolean isPopOrder(int[] pushV, int[] popV) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;

        for(int i = 0;i < pushV.length;i++) {
            stack.push(pushV[i]);
            while(!stack.isEmpty() && stack.peek() == popV[j] && j < popV.length) {
                stack.pop();
                j++;
            }
        }

        //return stack.isEmpty();
        return j>= popV.length;
    }
    public static void main6(String[] args) {
        int[] array1 = {1,2,3,4,5};
        int[] array2 = {4,1,3,2,5};
        System.out.println(isPopOrder(array1, array2));
    }
    /**
     * 最小栈->MinStack模拟实现
     * @param args
     */
    public static void main5(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin());//   --> 返回 -3.
        minStack.pop();
        System.out.println(minStack.top());//      --> 返回 0.
        System.out.println(minStack.getMin());//   --> 返回 -2.
    }
    /**
     * 有效的括号
     *      1.判断是否为空
     *      2.左括号入栈
     *      3.右括号出栈
     *      4.不等,直接false
     * @param s
     * @return
     */
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for(int i = 0;i < s.length();i++) {
            char ch = s.charAt(i);
            if(ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            }else {
                if(stack.isEmpty()) {
                    return false;
                }
                else {
                    char ch2 = stack.peek();

                    if(ch2 == '(' && ch == ')' || ch2 == '[' && ch == ']'
                            || ch2 == '{' && ch == '}') {
                        stack.pop();
                    }else {
                        return false;
                    }
                }
            }
        }
        if(stack.isEmpty()) {
            return true;
        }
        return false;
    }

    public static void main4(String[] args) {
        System.out.println(isValid("()"));
    }
    /**
     * 逆波兰表达式求值
     * @param args
     */
    /**
     1.判断是数字还是运算符
     2.数字入栈,运算符,出栈两个数字然后结果入栈
     */
    public static int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        int ret = 0;

        for(int i = 0;i < tokens.length;i++) {
            if(isOperator(tokens[i])) {//为字符
                int num1 = stack.pop();
                int num2 = stack.pop();
                switch(tokens[i]) {
                    case "+":
                        ret = num2 + num1;
                        break;
                    case "-":
                        ret = num2 - num1;
                        break;
                    case "*":
                        ret = num2 * num1;
                        break;
                    case "/":
                        ret = num2 / num1;
                        break;
                }
                stack.push(ret);
            }else {//为数字
                int val = Integer.valueOf(tokens[i]);
                stack.push(val);
            }
        }
        return stack.pop();
    }
    private static boolean isOperator(String str) {
        if(str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {
            return true;
        }
        return false;
    }
    public static void main3(String[] args) {
        String[] tokens = {"4","13","5","/","+"};
        System.out.println(evalRPN(tokens));
    }
    /**
     * 循环队列
     * @param args
     */
    public static void main2(String[] args) {
        MyCircularQueue myCircularQueue = new MyCircularQueue(2);
        myCircularQueue.enQueue(1);
        myCircularQueue.enQueue(2);
        myCircularQueue.deQueue();
        myCircularQueue.enQueue(3);
        myCircularQueue.deQueue();
        myCircularQueue.enQueue(3);
        myCircularQueue.deQueue();
        myCircularQueue.enQueue(3);
        myCircularQueue.deQueue();
        System.out.println(myCircularQueue.Front());
    }
    public static void main1(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(2);
        System.out.println(myStack.top()); // 返回 2
        System.out.println(myStack.pop()); // 返回 2
        System.out.println(myStack.empty()); // 返回 False
    }
}
